package someTestExcemple.huaweiOd.container.array;
import java.util.*;

//华为OD机试 - 简易内存池 - 逻辑分析（Java 2025 A卷 200分）
public class SimpleMemoryPool {
    static final String REQUEST = "REQUEST";
    static final String RELEASE = "RELEASE";
    static final String ERROR = "error";
    static final int MAX = 100;

    /**
     * 使用一个映射（如哈希表）来存储内存块的分配情况，键为内存块的首地址，值为内存块的结束地址。
     * @param args
     */
    public static void main(String[] args) {
        try {
            Scanner sc = new Scanner(System.in);
            // 操作命令的个数
            int N = Integer.parseInt(sc.nextLine());
            // 每一行的操作命令和参数
            String[][] lineArr = new String[N][2];
            // 接下来的N行，每行将给出一个操作命令，操作命令和参数之间用“=”分割
            for (int i = 0; i < N; i++) {
                lineArr[i] = sc.nextLine().split("=");
            }

            for (int i = 0; i < N; i++) {
                // 内存大小
                int value = Integer.parseInt(lineArr[i][1]);
                if (lineArr[i][0].startsWith(REQUEST)) {// 请求
                    // 非法输入（内存池总大小为100字节）
                    if (value > MAX || value <= 0) {
                        System.out.println(ERROR);
                        return;
                    }
                    request(value);
                } else if (lineArr[i][0].startsWith(RELEASE)) {// 释放
                    map.remove(value);
                } else {// 非法输入
                    System.out.println(ERROR);
                }
            }
        } catch (Exception e) {
            // 非法输入
            System.out.println(ERROR);
        }
    }

    /**
     * 存储内存的分配情况
     * key：内存的首地址
     * value：内存的尾地址
     * TreeMap：保证key的顺序
     */
    static Map<Integer, Integer> map = new TreeMap<>();

    /**
     * 请求内存
     *
     * @value：大小
     */
    public static void request(int value) {
        int zero = 0;
        // 前一个空闲区域的首地址
        int beforeHeadAddress = 0;

        // 如果map是空，放在首地址0处
        if (map.isEmpty()) {
            map.put(zero, value); //尾地址前一位才存值
        } else {
            // 已经存入的首地址
            List<Integer> headList = new ArrayList<>(map.keySet());
            // 已经存入的首地址
            for (Integer requestedHead : headList) {
                // 已经存入的首地址 - 第一个空闲区域的首地址 大于 请求的内存值
                if (requestedHead - beforeHeadAddress >= value) {
                    /**
                     * beforeHeadAddress：内存的首地址
                     * beforeHeadAddress + value：内存的尾地址
                     */
                    map.put(beforeHeadAddress, beforeHeadAddress + value);
                } else {
                    // 更新前一个空闲区域
                    beforeHeadAddress = map.get(requestedHead);
                }
            }
            // 判断剩余内存是否可以容下当前请求值
            if (MAX - beforeHeadAddress >= value) {
                map.put(beforeHeadAddress, beforeHeadAddress + value);
                System.out.println(beforeHeadAddress);
            } else {
                // 如果位置已满，则输出-1。
                System.out.println("-1");
            }
        }
    }
}

